from typing import List

inf = float('inf')


class Solution:
    def maxProfit(self, k: int, prices: List[int]) -> int:
        n = len(prices)
        dp = [[-inf] * (2 * k + 1) for _ in range(n)]
        for i in range(n):
            dp[i][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, n):
            for j in range(1, 2 * k + 1):
                t = (-1) ** (j & 1)
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + prices[i] * t)
        return max(dp[-1])


if __name__ == '__main__':
    s = Solution()
    r = s.maxProfit(k=2, prices=[2, 4, 1])
    print(r)
